Related Topics
Data Structure
What is a stack and how does it differ from a queue?
A stack and a queue are both abstract data types commonly used in computer science to store and manipulate collections of data.
A stack is a collection of elements that supports two main operations: push and pop. Push adds an element to the top of the stack, and pop removes and returns the element at the top of the stack. A stack follows the “last-in, first-out” (LIFO) principle, meaning that the most recently added element is the first one to be removed. A real-life example of a stack is a stack of plates: the top plate is the one that was added most recently and is the first one to be removed.
A queue, on the other hand, is a collection of elements that supports two main operations: enqueue and dequeue. Enqueue adds an element to the back of the queue, and dequeue removes and returns the element at the front of the queue. A queue follows the “first-in, first-out” (FIFO) principle, meaning that the first element to be added is the first one to be removed. A real-life example of a queue is a line of people waiting to buy tickets: the person who arrived first is the first one to be served.
The main difference between a stack and a queue is the order in which elements are added and removed. In a stack, the most recently added element is the first one to be removed, while in a queue, the first element to be added is the first one to be removed. This difference gives each data structure its own unique properties and use cases.
How to implement a stack using an array?
To implement a stack using an array in C, you can use the following steps:
Declare an array to hold the stack elements and an integer variable to hold the top index of the stack.
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
Push operation: To insert an element into the stack, increment the top variable and insert the element at the top of the stack.
void push(int element) {
if (top >= MAX_SIZE - 1) {
printf("Stack overflow!\n");
return;
}
stack[++top] = element;
}
Pop operation: To remove an element from the stack, return the element at the top of the stack and decrement the top variable.
int pop() {
if (top < 0) {
printf("Stack underflow!\n");
return -1;
}
return stack[top--];
}
Peek operation: To return the element at the top of the stack without removing it, simply return the element at the top index of the array.
int peek() {
if (top < 0) {
printf("Stack is empty!\n");
return -1;
}
return stack[top];
}
Check if stack is empty: To check if the stack is empty, simply check if the top variable is less than 0.
int is_empty() {
return top < 0;
}
How to implement a stack using a linked list?
To implement a stack using a linked list, we first need to define a Node class to represent the individual elements of the stack. Each Node should have a value attribute to store the actual value being added to the stack, as well as a next attribute to point to the next element in the stack.
Here’s an example implementation:
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.head = None
self.size = 0
def push(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
self.size += 1
def pop(self):
if self.head is None:
return None
else:
value = self.head.value
self.head = self.head.next
self.size -= 1
return value
def peek(self):
if self.head is None:
return None
else:
return self.head.value
def is_empty(self):
return self.size == 0
In this implementation, the Stack class keeps track of the head of the linked list (self.head) and the size of the stack (self.size). The push method adds a new element to the top of the stack by creating a new Node with the specified value and setting its next attribute to the current head of the list. The pop method removes the top element from the stack and returns its value, or returns None if the stack is empty. The peek method returns the value of the top element without removing it, or returns None if the stack is empty. The is_empty method returns True if the stack is empty and False otherwise.
What is the time complexity of push and pop operations in a stack?
The time complexity of push and pop operations in a stack depends on the underlying data structure used to implement the stack.
If a stack is implemented using an array, the time complexity of push and pop operations is O(1) (constant time) on average. However, in the worst case, when the array needs to be resized, the time complexity of push operation becomes O(n) (linear time), where n is the number of elements in the stack.
If a stack is implemented using a linked list, the time complexity of push and pop operations is also O(1) (constant time) on average, since the head of the linked list is used to insert or remove elements. In the worst case, the time complexity of these operations is also O(n) (linear time) if we need to traverse the entire list to find the head or tail.
How to reverse a string using a stack?
To reverse a string using a stack, we can push each character of the string onto the stack, then pop the characters off the stack and append them to a new string. Here is an example implementation in Python:
def reverse_string(string):
stack = []
for char in string:
stack.append(char)
reversed_string = ''
while len(stack) > 0:
reversed_string += stack.pop()
return reversed_string
In this implementation, we first create an empty stack and loop through each character of the input string. For each character, we push it onto the stack using the append() method.
Next, we create an empty string called reversed_string. We then enter a loop that continues as long as there are elements in the stack. Inside the loop, we use the pop() method to remove the top element from the stack and append it to the reversed_string. We repeat this process until the stack is empty.
Finally, we return the reversed_string.
How to check for balanced parentheses in an expression using a stack?
You can check for balanced parentheses in an expression using a stack by iterating through the expression and pushing every opening parentheses onto the stack. When a closing parentheses is encountered, pop the top element from the stack and check if it matches the closing parentheses. If the two do not match or the stack is empty before encountering the closing parentheses, then the expression is not balanced. Otherwise, continue iterating through the expression. If the stack is empty at the end of the iteration, then the expression is balanced.
Here is an example implementation in Python:
def check_balanced_parentheses(expression):
stack = []
for char in expression:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack:
return False
top = stack.pop()
if (char == ')' and top != '(') or \
(char == ']' and top != '[') or \
(char == '}' and top != '{'):
return False
return not stack
This implementation assumes that the expression only contains parentheses, square brackets, and curly braces, and no other characters. If the expression can contain other characters, you may need to modify the implementation accordingly.
Questions on Chapter 5