Let’s explore stacks and queues, which are one of the data structures frequently encountered in coding tests. Both data structures differ in how they store and process elements and can be selectively used depending on specific problems. In this course, we will look into the basic concepts of stacks and queues, algorithm problems utilizing these structures, and how to implement these problems in C++.
Stack
A stack is a structure for storing data based on the principle of Last In First Out (LIFO). This means that the most recently added data will be the first to be removed. The stack supports two main operations:
- push: Adds data to the top of the stack.
- pop: Removes data from the top of the stack and returns that data.
Examples of Stack Utilization
Stacks are useful for tasks like parentheses checking, reversing sets, and implementing backtracking functionality.
Queue
A queue is a structure for storing data based on the principle of First In First Out (FIFO). This means that the data that enters first will leave first. The main operations for queues are similarly as follows:
- enqueue: Adds data to the rear of the queue.
- dequeue: Removes data from the front of the queue and returns that data.
Examples of Queue Utilization
Queues are used in print job management, process scheduling, and implementing BFS (Breadth-First Search) algorithms.
Problem: Valid Parentheses String Check
This problem involves using a stack to check if the parentheses in a given string are valid. The definition of a valid parentheses string is as follows:
- All opened parentheses must have a corresponding closing parenthesis.
- Opened parentheses must not appear after their closing parentheses.
Problem Description
Given a string, you need to check if it is a valid parentheses string. The following cases can be considered “valid”:
- “()”
- “(())”
- “()()”
- “(()(()))”
Conversely, the following cases can be considered “invalid”:
- “)(“
- “(()”
- “())”
- “(()))”
Solution Process
To solve this problem, we will use a stack. Using the basic principle of a stack, we will add opened parentheses to the stack, and when a closed parenthesis appears, we will pop the opened parenthesis from the stack.
- Create an empty stack.
- Read the input string one character at a time.
- If the read character is ‘(‘, push it onto the stack.
- If the read character is ‘)’, check if the stack is not empty, then perform a pop operation on the stack. If the stack is empty, the string is invalid.
- After reading the entire string, if the stack is empty, the string is valid. If it’s not empty, the string is invalid.
C++ Code Implementation
The C++ code that implements the above algorithm is as follows:
#include <iostream>
#include <stack>
#include <string>
bool isValidParentheses(const std::string& str) {
std::stack s;
for (char c : str) {
if (c == '(') {
s.push(c);
} else if (c == ')') {
// If the stack is empty, it's an invalid parenthesis
if (s.empty()) {
return false;
}
s.pop(); // In a valid case, remove the opened parenthesis
}
}
// The stack must be empty at the end to be valid
return s.empty();
}
int main() {
std::string input;
std::cout << "Enter the parentheses string: ";
std::cin >> input;
if (isValidParentheses(input)) {
std::cout << "It is a valid parentheses string." << std::endl;
} else {
std::cout << "It is an invalid parentheses string." << std::endl;
}
return 0;
}
Result Testing
You can test various input strings with the above code. For example:
- Input:
()– Output: “It is a valid parentheses string.” - Input:
(())– Output: “It is a valid parentheses string.” - Input:
())– Output: “It is an invalid parentheses string.” - Input:
(()))– Output: “It is an invalid parentheses string.”
Summary and Tips
Stacks and queues play important roles in various algorithm problems. Stacks are primarily used for problems requiring LIFO structure, while queues are used for problems requiring FIFO structure. Through the problem-solving processes discussed in this course, I hope you have learned how to utilize stacks more effectively.