Stack and Queue slides Flashcards
How does the stack data structure flow?
A Stack is a linear data structure which follows a particular order in which operations are
performed. The order is LIFO (Last In First Out).
Think of it as: stack of books, plates and pringles potatoes chips
What are the first 2 types of operations on stack?
Push Operation:
Adds a new item to the top of the stack. If the stack isn’t at its maximum
capacity, the item is placed above the current top element, and the top
pointer updates to this new item.
Pop Operation:
Removes and returns the top item of the stack. If the stack isn’t empty, the
top item is removed, and the top pointer shifts to the next element down,
making it the new top.
What are the second 2 types of operations on stack?
Peek Operation:
Returns the top item of the stack without removing it, enabling a view of the
top item without altering the stack.
Checking if a Stack is Empty:
Determines if the stack has any elements by checking if the top pointer or
index indicates an empty state (e.g., -1
What are the 4 Practical Applications of stack?
Undo Mechanisms in Text Editors
Stacks record every edit in text editors or design software, allowing each
undo action to pop the most recent change off the stack and revert the
document to its prior state.
Syntax Parsing in Compilers
Compilers utilize stacks to parse and check the syntax of code, ensuring
structures like brackets and blocks open and close correctly.
Backtracking Algorithms (e.g., Maze Solving)
Stacks are used for algorithms that explore multiple paths, allowing for easy
backtracking to earlier points when necessary. This method is widely
applied in maze solving and search algorithms.
Function Call Management in Programming Languages
The call stack in programming languages manages function calls, storing
return addresses and parameters for each call. This facilitates the orderly
execution and return from function calls.
Understanding Queue
A Queue is a linear data structure that stores items in a First In, First Out (FIFO) manner. It is
analogous to a queue of people waiting in line, where the person at the front of the line is served
first, and new people join at the end of the line
What are the first 2 operations on Queue
Enqueue Operation:
Adds an item to the rear of the queue. This operation involves placing a new
element at the end of the queue, just as someone joining the back of a line.
Dequeue Operation:
Removes and returns the item from the front of the queue. Similar to the first
person in line being served and leaving the queue.
What are the second 2 operations on queue
Peek Operation:
Retrieves the item at the front of the queue without removing it, offering a
way to see the next item to be processed without altering the queue’s order.
Checking if a Queue is Empty:
Determines whether the queue has any elements by checking if the queue’s
size is zero or if its front pointer indicates an empty state, ensuring no
operations are attempted on an empty queue
What are the 3 Practical operations of queue?
1 .Task scheduling and management in operation systems
2. Handling of requests in web servers
3. Queueing theory in network traffic management
