Advertisement

Data-structures:

Data structures: lists,stack

According to CBSE academic session (2023-24)

What are data Structures?
A data structure is a way of organizing and storing data in a computer so that it can be accessed and manipulated efficiently. Data structures are the building blocks of algorithms, and they play a critical role in the design and implementation of efficient software.



__________________________________________________________________________________

List

-Lists are used to store multiple items in a single variable.

-Lists are one of 4 built-in data types in Python used to store collections of data, the other 3 are Tuple, Set, and Dictionaries, all with different qualities and usage.

-It is a collections of items and each item has its own index value. 

-Index of first item is 0 and the last item is n-1. Here n is the number of items in a list

-Lists are enclosed in square brackets [ ] and each item is separated by a comma.

list1 = [‘Computer', ‘Physics', 2020, 2023]; 

list2 = [11, 22, 33, 44, 55 ]; 

list3 = ["a", "b", "c", "d"]; 

Examples: 
my_list = [] #create empty list
print(my_list)
my_list = [1, 2, 3, 'example', 3.132] #creating list with data
print(my_list)

output
[]
[1, 2, 3, ‘example’, 3.132]

Access Items From A List

List items can be accessed using its index position

Examples:

list =[1,2,3] 

print(list[0]) 

print(list[1]) 

print(list[2]) 

print('Negative indexing') 

print(list[-1]) 

print(list[-2]) 

print(list[-3])

Output:
1
2
3
Negative indexing
3
2
1

List elements can be accessed using looping statement
Example:
list =[1,2,3] 
for i in range(0, len(list)):
        print(list[i]) 
output:
1
2
3
___________________________________________________________________________________

Stacks:

Stack data structures refer to the lists stored and accessed in a special way, where LIFO(Last In First Out) technique is followed.

Basic Operations of Stack

  • Push: Add an element to the top of a stack
  • Pop: Remove an element from the top of a stack
  • IsEmpty: Check if the stack is empty
  • IsFull: Check if the stack is full
  • Peek: Get the value of the top element without removing it

Applications of Stack in python

Stacks are a very versatile data structure, and they have a wide variety of applications in Python. Here are some of the most common applications of stacks in Python:

  • Evaluation of arithmetic expressions: Stacks can be used to evaluate expressions in infix, postfix, and prefix notations. In infix notation, operators are placed between operands. 
  • Backtracking: Backtracking is a recursive algorithm that can be used to solve problems by exploring all possible solutions. Stacks can be used to implement backtracking algorithms by storing the current state of the search. 
  • Undo/redo: Stacks can be used to implement undo/redo functionality in text editors, drawing programs, and other applications. This allows users to reverse their actions if they make a mistake.
  • Parsing: Stacks can be used to parse text, such as the source code of a programming language. 
  • Memory management: Stacks can be used to manage memory in a program. When a function is called, its arguments and local variables are pushed onto the stack. When the function returns, the arguments, and local variables are popped off the stack. This allows the memory used by the function to be released
Example:
stack = [1, 2, 3]
stack.append(4)
stack.append(10)
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
OUTPUT
[1, 2, 3, 4, 10]
10
[1, 2, 3, 4]
4
[1, 2, 3]

__________________________________________________________________________

Stack Implementations

Example:

# Creating a stack
def create_stack():
    stack = []
    return stack


# Creating an empty stack
def check_empty(stack):
    return len(stack) == 0


# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)


# Removing an element from the stack
def pop(stack):
    if (check_empty(stack)):
        return "stack is empty"

    return stack.pop()


stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))

Output: 
pushed item: 1
pushed item: 2
pushed item: 3
pushed item: 4
popped item: 4
stack after popping an element: ['1', '2', '3']