بررسی پشته (Stack)
پشته (Stack) یکی از پیاده‌سازی ها در ساختار داده است، در پشته (Stack) دسترسی به عناصر یک طرفه است و بر خلاف لیست که میتونیم به عناصر با index دسترسی داشته باشیم در پشته فقط میتونیم آخرین عنصری که اضافه کردیم رو صدا بزنیم و برای دسترسی به عنصر بعدی باید آخرین عنصر از Stack خارج (حذف) بشه و پشته (Stack) معروفه به last-in-first-out به زبون خودمونی دیر اومدی میخوای زود بری :)
یک لیوان رو در نظر بگیرید که داخلش میخوایم چندتا توپ بندازیم، برای دسترسی به اولین توپی که انداختیم، باید توپ های بعدی رو بیاریم بیرون؛ نگهداری، دسترسی و حذف عناصر در استک (Stack) شبیه همینه.
پشته (Stack) رو میتونیم با استفاده از آرایه ها با سایز ثابت یا با لیست پیوندی (LinkedList) پیاده‌سازی کنیم؛ در این مطلب به پیاده‌سازی استک با لیست پیوندی می پردازیم.
میتونیم یک پشته (Stack) رو با رابطه ی aggregation یا inheritance توسط لیست پیوندی پیاده‌سازی کنیم؛ که در اینجا به پیاده‌سازی استک با لیست پیوندی با روش aggregation می پردازیم.
افزودن عنصر به پشته (Stack)
به طور عمومی با تابع push(e: E) میتونیم یک عنصر رو به استک اضافه کنیم، ولی ممکنه در زبان های برنامه نویسی مختلف این اسم فرق کنه؛ پیچیدگی زمان برای اضافه کردن یک عنصر به استک O(1) است.
function push(e: E){
linkedList.addLast(e);
}
حذف عنصر از پشته (Stack)
به طور عمومی برای حذف یک عنصر از تابع pop(): E در استک استفاده می کنیم، ممکنه اسم pop():E در زبان های مختلف فرق کنه؛ آخرین عنصری که به استک اضافه می کنیم، اولین عنصری خواهد بود که از استک حذف میشه و تا زمانی که این عنصر از پشته (Stack) حذف نشه به عنصر بعدی دسترسی نخواهیم داشت.
پیچیدگی زمان برای حذف یک عنصر از استک O(1) است.
function pop(): E{
return linkedList.removeLast()
}
صدا زدن عنصر از پشته (Stack)
به طور عمومی با تابع peek(): E برای صدا زدن یک عنصر از پشته (Stack) استفاده می کنیم، نام این تابع ممکنه در زبان های برنامه نویسی مختلف فرق کنه؛ با تابع peek میتونیم به آخرین عنصری که به استک اضافه کردیم دسترسی داشته باشیم و برای دسترسی به عنصر بعدی با peek باید عنصر فعلی حذف بشه.
پیچیدگی زمان برای صدا زدن عنصر از استک O(1) است
function peek(): E{
return linkedList.getLast()
}
پیاده‌سازی استک در زبان های برنامه نویسی
در اینجا میخوایم با استفاده از لیست پیوندی که پیاده کردیم، استک رو در زبان های برنامه نویسی جاوا، کاتلین، جاوااسکریپت و پایتون پیاده‌سازی کنیم.
در زیر پیاده‌سازی پشته (Stack) به صورت uml آورده شده است.
برای راحتی یک دسترسی سریع به پیاده‌سازی ها با زبان های مختلف رو در زیر قرار دادیم.
پیاده‌سازی پشته (Stack) با جاوا
در زیر یک پشته (Stack) رو به صورت جنریک با جاوا پیاده میکنیم.
public class MyStack<E> {
private final MyLinkedList<E> list = new MyLinkedList<>();
public MyStack(E[] elements){
for (int i=0; i<elements.length; i++){
list.addLast(elements[i]);
}
}
public MyStack(){
}
public E pop(){
if (list.isEmpty()) return null;
return list.removeLast();
}
public void push(E e){
list.addLast(e);
}
public E peek(){
if (list.isEmpty()) return null;
return list.getLast();
}
public boolean isEmpty(){
return list.isEmpty();
}
public int getSize(){
return list.getSize();
}
}
پیاده‌سازی پشته (Stack) با کاتلین
در زیر یک صف (Queue) رو با کاتلین به صورت جنریک پیاده‌سازی میکنیم.
class MyStack<E>() {
private val list: MyLinkedList<E> = MyLinkedList()
val isEmpty: Boolean
get() = list.size == 0
val size: Int
get() = list.size
constructor(elements: Array<E>): this() {
for (i in elements.indices) {
list.addLast(elements[i])
}
}
fun pop(): E? {
if (list.empty) return null
return list.removeLast()
}
fun push(e: E) {
list.addLast(e)
}
fun peek(): E? {
if (list.empty) return null
return list.getLast()
}
}
پیاده‌سازی پشته (Stack) با جاوااسکریپت
جاوااسکریپت یک زبان type-free است یعنی نوع متغیر هنگام مقداردهی متغیر مشخص میشه، در زیر یک صف (Queue) رو با جاوااسکریپت پیاده میکنیم.
class MyStack {
constructor(elements = null) {
this.list = new MyLinkedList();
if (elements !== null) {
for (let i = 0; i < elements.length; i++) {
this.list.addLast(elements[i]);
}
}
}
pop() {
if (this.list.isEmpty()) return null;
return this.list.removeLast();
}
push(e) {
this.list.addLast(e);
}
peek() {
if (this.list.isEmpty()) return null;
return this.list.getLast();
}
isEmpty() {
return this.list.isEmpty();
}
getSize() {
return this.list.getSize();
}
}
پیاده‌سازی پشته (Stack) با پایتون
پایتون یک زبان type-free است یعنی نوع متغیر هنگام مقداردهی متغیر مشخص میشه، در زیر یک پشته (Stack) با پایتون پیاده میکنیم.
import MyLinkedList
class MyStack:
def __init__(self, elements=None):
self.list = MyLinkedList()
if elements is not None:
for i in range(len(elements)):
self.list.add_last(elements[i])
def pop(self):
if self.list.isEmpty():
return None
return self.list.remove_last()
def push(self, e):
self.list.add_last(e)
def peek(self):
if self.list.is_empty():
return None
return self.list.get_last()
def is_empty(self):
return self.list.is_empty()
def get_size(self):
return self.list._size
استفاده از پشته (Stack) در زبان های برنامه نویسی
میخوایم با استفاده از پشته (Stack) یک پروژه ی ماشین حساب بنویسیم، در این پروژه یک عبارت مثل 2*5+(4/2)-32 حساب کنه.
این پروژه با استفاده از پیاده‌سازی های بالا نوشته شده است.
public class EvaluateExpression {
public double evaluateExpression(String expression) {
MyStack<Double> operands = new MyStack<>();
MyStack<Character> operators = new MyStack<>();
expression = expression.trim(); //remove every space in expression
expression = insertBlanks(expression);
String[] tokens = expression.split("\\s");
for (String token : tokens) {
if (!token.isEmpty()) {
if (token.charAt(0) == '+' || token.charAt(0) == '-') {
while (
!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '-' || operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')
) {
processAnOperation(operators, operands);
}
operators.push(token.charAt(0));
} else if (token.charAt(0) == '*' || token.charAt(0) == '/' || token.charAt(0) == '^') {
while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')) {
processAnOperation(operators, operands);
}
operators.push(token.charAt(0));
} else if (token.charAt(0) == '(') {
operators.push('(');
} else if (token.charAt(0) == ')') {
while (operators.peek() != '(') {
processAnOperation(operators, operands);
}
operators.pop();
} else {
operands.push(Double.parseDouble(token));
}
}
}
while (!operators.isEmpty())
processAnOperation(operators, operands);
return operands.pop();
}
private static void processAnOperation(Stack<Character> operators, Stack<Double> operands) {
char op = operators.pop();
double operand0 = operands.pop();
double operand1 = operands.pop();
switch (op) {
case '*' -> operands.push(operand1 * operand0);
case '/' -> operands.push(operand1 / operand0);
case '-' -> operands.push(operand1 - operand0);
case '+' -> operands.push(operand1 + operand0);
case '^' -> operands.push(Math.pow(operand1, operand0));
}
}
private static String insertBlanks(String s) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
result.append(" ").append(ch).append(" ");
else result.append(ch);
}
return result.toString();
}
}
fun evaluateExpression(expression: String): Double {
var expression = expression
val operands = MyStack<Double>()
val operators = MyStack<Char>()
expression = expression.trim() //remove every space in expression
expression = insertBlanks(expression)
val tokens = expression.split(Regex("\\s"))
for (token in tokens) {
if (!token.isEmpty()) {
if (token[0] == '+' || token[0] == '-') {
while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '-' || operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')
) {
processAnOperation(operators, operands)
}
operators.push(token[0])
} else if (token[0] == '*' || token[0] == '/' || token[0] == '^') {
while (!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '^')) {
processAnOperation(operators, operands)
}
operators.push(token[0])
} else if (token[0] == '(') {
operators.push('(')
} else if (token[0] == ')') {
while (operators.peek() != '(') {
processAnOperation(operators, operands)
}
operators.pop()
} else {
operands.push(token.toDouble())
}
}
}
while (!operators.isEmpty()) processAnOperation(operators, operands)
return operands.pop()
}
private fun processAnOperation(operators: Stack<Char>, operands: Stack<Double>) {
val op: Char = operators.pop()
val operand0: Double = operands.pop()
val operand1: Double = operands.pop()
when (op) {
'*' -> operands.push(operand1 * operand0)
'/' -> operands.push(operand1 / operand0)
'-' -> operands.push(operand1 - operand0)
'+' -> operands.push(operand1 + operand0)
'^' -> operands.push(operand1.pow(operand0))
}
}
private fun insertBlanks(s: String): String {
val result = StringBuilder()
for (i in s.indices) {
val ch = s[i]
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')') result.append(" ")
.append(ch).append(" ")
else result.append(ch)
}
return result.toString()
}
class EvaluateExpression {
evaluateExpression(expression) {
let operands = new MyStack();
let operators = new MyStack();
expression = expression.trim();
expression = this.insertBlanks(expression);
String.prototype.split
let tokens = expression.split(/\s+/);
for (let i = 0; i < tokens.length; i++) {
let token = tokens[i];
if (token.length > 0) {
if (token.charAt(0) === '+' || token.charAt(0) === '-') {
while (
!operators.isEmpty() &&
(operators.peek() === '*' || operators.peek() === '-' ||
operators.peek() === '*' || operators.peek() === '/')
) {
this.processAnOperation(operators, operands);
}
operators.push(token.charAt(0));
} else if (token.charAt(0) === '*' || token.charAt(0) === '/') {
while (!operators.isEmpty() && (operators.peek() === '*' || operators.peek() === '/') {
this.processAnOperation(operators, operands);
}
operators.push(token.charAt(0));
} else if (token.charAt(0) === '(') {
operators.push('(');
} else if (token.charAt(0) === ')') {
while (operators.peek() !== '(') {
this.processAnOperation(operators, operands);
}
operators.pop();
} else {
operands.push(parseFloat(token));
}
}
}
while (!operators.isEmpty()) {
this.processAnOperation(operators, operands);
}
return operands.pop();
}
processAnOperation(operators, operands) {
let op = operators.pop();
let operand0 = operands.pop();
let operand1 = operands.pop();
switch (op) {
case '*': operands.push(operand1 * operand0); break;
case '/': operands.push(operand1 / operand0); break;
case '-': operands.push(operand1 - operand0); break;
case '+': operands.push(operand1 + operand0); break;
}
}
insertBlanks(s) {
let result = "";
for (let i = 0; i < s.length; i++) {
let ch = s.charAt(i);
if (ch === '+' || ch === '-' || ch === '*' || ch === '/' || ch === '(' || ch === ')')
result += " " + ch + " ";
else result += ch;
}
return result;
}
}
import re
class EvaluateExpression:
def evaluate_expression(self, expression):
operands = MyStack()
operators = MyStack()
expression = expression.strip()
expression = self.insert_blanks(expression)
tokens = re.split(r'\s+', expression)
for token in tokens:
if len(token) > 0:
if token[0] == '+' or token[0] == '-':
while (
not operators.is_empty() and (operators.peek() == '*' or operators.peek() == '-' or operators.peek() == '*' or operators.peek() == '/')
):
self.process_an_operation(operators, operands)
operators.push(token[0])
elif token[0] == '*' or token[0] == '/' or token[0] == '^':
while not operators.is_empty() and (operators.peek() == '*' or operators.peek() == '/'):
self.process_an_operation(operators, operands)
operators.push(token[0])
elif token[0] == '(':
operators.push('(')
elif token[0] == ')':
while operators.peek() != '(':
self.process_an_operation(operators, operands)
operators.pop()
else:
operands.push(float(token))
while not operators.is_empty():
self.process_an_operation(operators, operands)
return operands.pop()
def process_an_operation(self, operators, operands):
op = operators.pop()
operand0 = operands.pop()
operand1 = operands.pop()
if op == '*': operands.push(operand1 * operand0)
elif op == '/': operands.push(operand1 / operand0)
elif op == '-': operands.push(operand1 - operand0)
elif op == '+': operands.push(operand1 + operand0)
def insert_blanks(self, s):
result = []
for i in range(len(s)):
ch = s[i]
if ch == '+' or ch == '-' or ch == '*' or ch == '/' or ch == '(' or ch == ')':
result.append(" " + ch + " ")
else:
result.append(ch)
return "".join(result)
خلاصه
- استک یک ساختار داده ی یک طرفه است.
- در پشته (Stack) آخرین عنصری که وارد میکنیم اولین عنصریه که میتونیم صدا بزنیم یا حذف کنیم.
- ساختار عناصر (داده ها) در استک به last-in-first-out معروف است.
- در پشته (Stack) به فقط به آخرین عنصری که اضافه کردیم دسترسی داریم و تا زمانی که حذف نشده به عناصر بعدی دسترسی نخواهیم داشت.
- با استفاده از آرایه ها میتونیم یک استک با اندازه ی ثابت و با استفاده از لیست پیوندی میتونیم یک استک با اندازه ی متغیر پیاده‌سازی کنیم.
- پیچیدگی زمان برای اضافه و حذف کردن و صدا زدن عنصر در استک O(1) است.
بازخورد و دیدگاه ها
اولین نفری باشید که در این صفحه نظر می‌دهید