e-olymp 6122. Простой стек

30/06/2017 by Шостак Дмитрий

Задача

Формулировка задания на e-olymp.

Реализуйте структуру данных «стек». Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n — Добавить в стек число n (значение n задается после команды). Вывести ok.
pop — Удалить из стека последний элемент. Программа должна вывести его значение.
back — Вывести значение последнего элемента, не удаляя его из стека.
size — Вывести количество элементов в стеке.
clear — Очистить стек и вывести ok.
exit — Вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Входные данные

Каждая строка содержит одну команду.

Выходные данные

Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

Входные данные	Выходные данные
push 2 push 3 push 5 back size pop size push 7 pop clear size exit	ok ok ok 5 3 5 2 ok 7 ok 0 bye

Отмечу так же, что программа успешно прошла все тесты на сайте e-olymp со следующими результатами.

Решение

class Stack {

	Vector<Integer> storage;
	
	public Stack()
	{
		storage = new Vector<Integer>();
	}
	
	void push(int number)
	{
		this.storage.add(number);
	}
	
	int pop()
	{
		int lastNumber = storage.lastElement();
		storage.remove(storage.size() - 1);
		return lastNumber;
	}
	
	int back()
	{
		int lastNumber = storage.lastElement();
		return lastNumber;
	}
	
	int size()
	{
		return storage.size();
	}
	
	void clear()
	{
		storage.clear();
	}
	
	String exit()
	{
		return "bye";
	}
	
}


public class Main {

	public static void main(String[] args) {
		Stack stack = new Stack();
		Scanner input = new Scanner(System.in);
		int number;
		String request;
		while(input.hasNextLine())
		{	
			request = input.next();
			if(request.equals("push"))
			{
				number = input.nextInt();
				stack.push(number);
				System.out.println("ok");
			}
			else if(request.equals("pop")) System.out.println(stack.pop());
			else if(request.equals("back")) System.out.println(stack.back());
			else if(request.equals("size")) System.out.println(stack.size());
			else if(request.equals("clear")) 
			{
				stack.clear();
				System.out.println("ok");
			}
			else if(request.equals("exit"))
			{
				System.out.println(stack.exit());
				break;
			}
		}
	}
}

class Stack {

Vector<Integer> storage;

public Stack()

{

storage = new Vector<Integer>();

}

void push(int number)

{

this.storage.add(number);

}

int pop()

{

int lastNumber = storage.lastElement();

storage.remove(storage.size() - 1);

return lastNumber;

}

int back()

{

int lastNumber = storage.lastElement();

return lastNumber;

}

int size()

{

return storage.size();

}

void clear()

{

storage.clear();

}

String exit()

{

return "bye";

}

public class Main {

public static void main(String[] args) {

Stack stack = new Stack();

Scanner input = new Scanner(System.in);

int number;

String request;

while(input.hasNextLine())

{

request = input.next();

if(request.equals("push"))

{

number = input.nextInt();

stack.push(number);

System.out.println("ok");

}

else if(request.equals("pop")) System.out.println(stack.pop());

else if(request.equals("back")) System.out.println(stack.back());

else if(request.equals("size")) System.out.println(stack.size());

else if(request.equals("clear"))

{

stack.clear();

System.out.println("ok");

}

else if(request.equals("exit"))

{

System.out.println(stack.exit());

break;

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Структура класса Stack из себя представляет следующее:

Динамический массив storage типа Vector<Integer> , который, по сути, и является хранилищем элементов стека;
Конструктор, в котором происходит инициализация вектора storage ;
Метод push(int number) типа void , который принимает как параметр число, и заносит это число в стек;
Метод pop() типа int , который возвращает значение верхнего элемента стека и извлекает его;
Метод back() типа int , который возвращает значение верхнего элемента стека, без его извлечения;
Метод size() , который возвращает количество элементов, находящихся в стеке;
Метод clear() , который очищает стек;
Метод exit() типа String , который возвращает строку «bye».

e-olymp 6127. The queue of unlimited size

31/08/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

Программа должна вывести значение первого элемента, не удаляя его из очереди.

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

Входные данные

Описаны в условии. См. также пример входных данных.

Выходные данные

Описаны в условии. См. также пример выходных данных.

Тесты:

№	Входные данные	Выходные данные:
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static class Node {
		public int value;
		public Node next;
		
		public Node() {
			value = 0;
			next = null;
		}
		public Node(int newValue, Node newNext) {
			value = newValue;
			next = newNext;
		}
	}
	
	public static class Queue {
		private int size;
		private Node first;
		private Node last;
		
		public Queue() {
			size = 0;
			first = null;
			last = null;
		}
		
		public void push(int v) {
			Node newNode = new Node(v, null);
			if (size == 0) {
				first = last = newNode;
			} else {
				last.next = newNode;
				last = newNode;
			}
			size++;
		}
		public boolean pop() {
			boolean ret = false;
			if (size > 0) {
				int val = first.value;
				first = first.next;
				size--;
				System.out.println(val);
				ret = true;
			}
			return ret;
		}
		public boolean front() {
			boolean ret = false;
			if (size > 0) {
				System.out.println(first.value);
				ret = true;
			}
			return ret;
		}
		public int getSize() {
			return size;
		}
		public void clear() {
			first = null;
			last = null;
			size = 0;
		}
	}
	public static void main(String[] args) {
		Queue q = new Queue();
		String s;
		int n;
		Scanner scan = new Scanner(System.in);
		while ((s = scan.next()) != null) {
			switch(s) {
				case "size": System.out.println(q.getSize()); break;
				case "push":
					n = scan.nextInt();
					q.push(n);
					System.out.println("ok");
					break;
				case "pop":
					if (q.pop() == false) {
						System.out.println("error");
					}
					break;
				case "front":
					if (q.front() == false) {
						System.out.println("error");
					}
					break;
				case "clear":
					q.clear();
					System.out.println("ok");
					break;
				case "exit":
					System.out.println("bye");
					return;
				default: break;
			}
		}
	}
}

100

101

102

103

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static class Node {

public int value;

public Node next;

public Node() {

value = 0;

next = null;

}

public Node(int newValue, Node newNext) {

value = newValue;

next = newNext;

}

public static class Queue {

private int size;

private Node first;

private Node last;

public Queue() {

size = 0;

first = null;

last = null;

}

public void push(int v) {

Node newNode = new Node(v, null);

if (size == 0) {

first = last = newNode;

} else {

last.next = newNode;

last = newNode;

}

size++;

}

public boolean pop() {

boolean ret = false;

if (size > 0) {

int val = first.value;

first = first.next;

size--;

System.out.println(val);

ret = true;

}

return ret;

}

public boolean front() {

boolean ret = false;

if (size > 0) {

System.out.println(first.value);

ret = true;

}

return ret;

}

public int getSize() {

return size;

}

public void clear() {

first = null;

last = null;

size = 0;

}

public static void main(String[] args) {

Queue q = new Queue();

String s;

int n;

Scanner scan = new Scanner(System.in);

while ((s = scan.next()) != null) {

switch(s) {

case "size": System.out.println(q.getSize()); break;

case "push":

n = scan.nextInt();

q.push(n);

System.out.println("ok");

break;

case "pop":

if (q.pop() == false) {

System.out.println("error");

}

break;

case "front":

if (q.front() == false) {

System.out.println("error");

}

break;

case "clear":

q.clear();

System.out.println("ok");

break;

case "exit":

System.out.println("bye");

return;

default: break;

}

Алгоритм:

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Для этого соответствующие методы делаем логическими.

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olimp 6129. Дек неограниченного размера

28/08/2016 by Ирина Литвиненко

Задача:

Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Тесты:

Последовательность

Результат

push_front
4
push_back
5
front
push_front
3
back
size
pop_front
pop_back
clear
pop_back
size
exit

4
ok

5
3
3
5
ok
error
0
bye

import java.util.Scanner;

public class Deque {

    private class Node {
        Node prev;
        Node next;
        int x;

        Node() {
            prev = null;
            next = null;
            x = 0;
        }
        Node(Node a, Node b, int c) {
            prev = a;
            next = b;
            x = c;
        }
    };

    Node Front = null;
    Node Back = null;
    int Size = 0;

    int size() {
        return Size;
    }

    void push_back(int p) {
        if (Size == 0) {
            Node NewNode = new Node(Back, Front, p);
            Front = NewNode;
            Back = NewNode;
        } else {
            Node NewNode = new Node(null, Back, p);
            Back.prev = NewNode;
            Back = NewNode;
        }
        Size++;
    }

    void push_front(int p) {
        if (Size == 0) {
            Node NewNode = new Node(Back, Front, p);
            Front = NewNode;
            Back = NewNode;
        } else {
            Node NewNode = new Node(Front, null, p);
            Front.next = NewNode;
            Front = NewNode;
        }
        Size++;
    }

    int back() {
        if (Size != 0) {
            return Back.x;
        } else {
            return 0;
        }
    }

    int front() {
        if (Size != 0) {
            return Front.x;
        } else {
            return 0;
        }
    }

    int pop_front() {
        if (Size != 0) {
            int x = Front.x;
            Node NewNode = Front.prev;
            Front = NewNode;
            Size--;
            return x;
        } else {
            return 0;
        }
    }

    int pop_back() {
        if (Size != 0) {
            int x = Back.x;
            Node NewNode = Back.next;
            Back = NewNode;
            Size--;
            return x;
        } else {
            return 0;
        }
    }

    void clear() {
        while (Size > 0) {
            Node NewNode = Front.prev;
            Front = NewNode;
            Size--;
        }
        Front = null;
        Back = null;
    }


    public static void main(String[] args) {
        Deque deque = new Deque();
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter your command");
        String command = scanner.nextLine();

        while (!command.equals("exit")) {
            if (command.equals("push_back")) {
                int v = scanner.nextInt();
                deque.push_back(v);
                System.out.println("ok\n");
            } else if (command.equals("push_front")) {
                int v = scanner.nextInt();
                deque.push_front(v);
                System.out.println("ok\n");
            } else if (command.equals("front")) {
                if (deque.size() > 0) {
                    System.out.println(deque.front());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("back")) {
                if (deque.size() > 0) {
                    System.out.println(deque.back());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("size")) {
                System.out.println(deque.size());
            } else if (command.equals("pop_front")) {
                if (deque.size() > 0) {
                    System.out.println(deque.pop_front());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("pop_back")) {
                if (deque.size() > 0) {
                    System.out.println(deque.pop_back());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("clear")) {
                System.out.println("ok\n");
                deque.clear();
            }
            command = scanner.nextLine();
        }
        System.out.println("bye");
    }
};

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

import java.util.Scanner;

public class Deque {

private class Node {

Node prev;

Node next;

int x;

Node() {

prev = null;

next = null;

x = 0;

}

Node(Node a, Node b, int c) {

prev = a;

next = b;

x = c;

}

};

Node Front = null;

Node Back = null;

int Size = 0;

int size() {

return Size;

}

void push_back(int p) {

if (Size == 0) {

Node NewNode = new Node(Back, Front, p);

Front = NewNode;

Back = NewNode;

} else {

Node NewNode = new Node(null, Back, p);

Back.prev = NewNode;

Back = NewNode;

}

Size++;

}

void push_front(int p) {

if (Size == 0) {

Node NewNode = new Node(Back, Front, p);

Front = NewNode;

Back = NewNode;

} else {

Node NewNode = new Node(Front, null, p);

Front.next = NewNode;

Front = NewNode;

}

Size++;

}

int back() {

if (Size != 0) {

return Back.x;

} else {

return 0;

}

int front() {

if (Size != 0) {

return Front.x;

} else {

return 0;

}

int pop_front() {

if (Size != 0) {

int x = Front.x;

Node NewNode = Front.prev;

Front = NewNode;

Size--;

return x;

} else {

return 0;

}

int pop_back() {

if (Size != 0) {

int x = Back.x;

Node NewNode = Back.next;

Back = NewNode;

Size--;

return x;

} else {

return 0;

}

void clear() {

while (Size > 0) {

Node NewNode = Front.prev;

Front = NewNode;

Size--;

}

Front = null;

Back = null;

}

public static void main(String[] args) {

Deque deque = new Deque();

Scanner scanner = new Scanner(System.in);

System.out.println("enter your command");

String command = scanner.nextLine();

while (!command.equals("exit")) {

if (command.equals("push_back")) {

int v = scanner.nextInt();

deque.push_back(v);

System.out.println("ok\n");

} else if (command.equals("push_front")) {

int v = scanner.nextInt();

deque.push_front(v);

System.out.println("ok\n");

} else if (command.equals("front")) {

if (deque.size() > 0) {

System.out.println(deque.front());

} else {

System.out.println("error\n");

}

} else if (command.equals("back")) {

if (deque.size() > 0) {

System.out.println(deque.back());

} else {

System.out.println("error\n");

}

} else if (command.equals("size")) {

System.out.println(deque.size());

} else if (command.equals("pop_front")) {

if (deque.size() > 0) {

System.out.println(deque.pop_front());

} else {

System.out.println("error\n");

}

} else if (command.equals("pop_back")) {

if (deque.size() > 0) {

System.out.println(deque.pop_back());

} else {

System.out.println("error\n");

}

} else if (command.equals("clear")) {

System.out.println("ok\n");

deque.clear();

}

command = scanner.nextLine();

}

System.out.println("bye");

}

};

Решение

Решение на Ideone
Дек — (двухсторонняя очередь) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO. Для реализации дека неограниченного размера удобно использовать двусвязный список.

e-olymp 6123. Стек с защитой от ошибок

26/08/2016 by Дарья Пиндус

Задача

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

Программа должна вывести значение последнего элемента, не удаляя его из стека.

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Входные данные

Команды для стека.

Выходные данные

Соответствующие значения для каждой команды(см. выше).

Тесты

№	Последовательность	Результат
1	push 2 back pop size pop push 1 size exit	ok 2 2 0 error ok 1 bye
2	push 3 push 1 push 5 size pop size exit	ok ok ok 3 5 2 bye
3	back push 9 pop pop exit	error ok 9 error bye
4	size push 1 size back pop exit	0 ok 1 1 1 bye

Код

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
class Stack {
 
    private int pointer;
    private int[] stack;
    private int size;
 
 
    public Stack() {
        this(20);
    }
 
    public Stack(int capacity) {
            size = capacity;
            stack = new int[size];
            pointer = -1;
    }
 
    public void push(int element) {
        stack[++pointer] = element;
    }
 
    public int pop() {
        int i = stack[pointer];
        stack[pointer--] = 0;
        return i;
    }
 
    public int back() {
        return stack[pointer];
    }
 
    public void clear() {
        Arrays.fill(stack, 0);
        pointer = -1;
    }
 
    public boolean isEmpty() {
        if (pointer < 0)
            return true;
        else
            return false;
    }
 
    public int size() {
        return this.pointer + 1;
    }
 
    public static void main(String[] args) {
        Stack stack = new Stack();
 
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter your command");
        String command = scanner.nextLine();
 
        while (!command.equals("exit")) {
            if (command.matches("^push [0-9]")) {
                String[] comm = command.split(" ");
                stack.push(Integer.parseInt(comm[1]));
                System.out.println("OK");
            } else if (command.equals("pop")) {
                if (stack.isEmpty()) {
                    System.out.println("Error. Stack is empty");
                } else {
                    System.out.println(stack.pop());
                }
            } else if (command.equals("size")) {
                System.out.println(stack.size());
            } else if (command.equals("back")) {
                if (stack.isEmpty()) {
                    System.out.println("Error. Stack is empty");
                } else {
                    System.out.println(stack.back());
                }
            } else if (command.equals("clear")) {
                stack.clear();
                System.out.println("OK");
            } else {
                System.out.println("Command doesn't exist");
            }
            command = scanner.nextLine();
        }
        System.out.println("bye");
 
    }
}

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;

class Stack {

private int pointer;

private int[] stack;

private int size;

public Stack() {

this(20);

}

public Stack(int capacity) {

size = capacity;

stack = new int[size];

pointer = -1;

}

public void push(int element) {

stack[++pointer] = element;

}

public int pop() {

int i = stack[pointer];

stack[pointer--] = 0;

return i;

}

public int back() {

return stack[pointer];

}

public void clear() {

Arrays.fill(stack, 0);

pointer = -1;

}

public boolean isEmpty() {

if (pointer < 0)

return true;

else

return false;

}

public int size() {

return this.pointer + 1;

}

public static void main(String[] args) {

Stack stack = new Stack();

Scanner scanner = new Scanner(System.in);

System.out.println("enter your command");

String command = scanner.nextLine();

while (!command.equals("exit")) {

if (command.matches("^push [0-9]")) {

String[] comm = command.split(" ");

stack.push(Integer.parseInt(comm[1]));

System.out.println("OK");

} else if (command.equals("pop")) {

if (stack.isEmpty()) {

System.out.println("Error. Stack is empty");

} else {

System.out.println(stack.pop());

}

} else if (command.equals("size")) {

System.out.println(stack.size());

} else if (command.equals("back")) {

if (stack.isEmpty()) {

System.out.println("Error. Stack is empty");

} else {

System.out.println(stack.back());

}

} else if (command.equals("clear")) {

stack.clear();

System.out.println("OK");

} else {

System.out.println("Command doesn't exist");

}

command = scanner.nextLine();

}

System.out.println("bye");

}

Решение

Создаем структуру в которой реализуем все команды для стека с помощью функций и указателя $cursor$ . $cursor$ указывает на последний элемент в строке. Изначально $cursor$ , т.к. элементы в массиве, на которые бы он указывал, отсутствуют.

$push n$ записывает в ячейку с номером $cursor$ элемент $n$ . $size$ возвращает $cursor$ т.е. действительный размер стека. $pop$ возвращает последний помещённый в стек элемент, то есть элемент с номером $pointer+1$ , при этом удаляя его из стека. $back$ возвращает последний помещённый в стек элемент, то есть элемент с номером $cursor-1$ .В обоих случаях для проверки того, пуст ли стек, используется логическая функция $error$ . $clear$ обнуляет массив $cursor$ и присваивает $cursor$ начальное значение = -1.Команды считываются и выполняются пока не будет введено $exit$ , после чего выведется соответствующее сообщение и программа завершится.

Ссылка на Ideone

e-olymp 6125. Простая очередь

22/07/2016 by Артур Тарасов

Задача

Реализуйте структуру данных «очередь». Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
size — Программа должна вывести количество элементов в очереди.
clear — Программа должна очистить очередь и вывести ok.
exit — Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Данную задачу также можно найти здесь.

Входные данные

Описаны в условии. Смотрите также тесты, расположенные ниже.

Выходные данные

Описаны в условии. Смотрите также тесты, расположенные ниже.

Тесты

№	Входные данные	Выходные данные
1	push 123 size push -5 pop exit	ok 1 ok 123 bye
2	push 1 push 2 front push 42 pop exit	ok ok 1 ok 1 bye
3	push 1 push 2 pop pop size exit	ok ok 1 2 0 bye

Код

import java.util.*;
import java.lang.*;
import java.io.*;

class MyQueue {
    int[] storage = new int[100];
    int start;
    int finish;
    MyQueue() {
        start = 0;
        finish = 0;
    }
    void push(int n) {
        storage[finish] = n;
        finish++;
    }
    int pop() {
        int a = storage[start];
        start++;
        return a;
    }
    int front() {
        return storage[start];
    }
    int size() {
        return finish - start;
    }
    String clear() {
        finish = 0;
        start = 0;
        return "ok";
    }
    String exit() {
        return "bye";
    }
}

public class Main {
	public static void main(String[] args) throws java.lang.Exception {
		String a;
		MyQueue x = new MyQueue();
		try (Scanner sc = new Scanner(System.in)) {
			while (sc.hasNextLine()){
				a = sc.next();
				if (a.equals("push")) {
					int n;
					n = sc.nextInt();
					x.push(n);
					System.out.println("ok");
				}
				if (a.equals("pop")) {
					System.out.println(x.pop());
				}
				if (a.equals("front")) {
					System.out.println(x.front());
				}
				if (a.equals("size")) {
					System.out.println(x.size());
				}
				if (a.equals("clear")) {
					System.out.println(x.clear());
				}
				if (a.equals("exit")) {
					System.out.println(x.exit());
					break;
				}
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class MyQueue {

int[] storage = new int[100];

int start;

int finish;

MyQueue() {

start = 0;

finish = 0;

}

void push(int n) {

storage[finish] = n;

finish++;

}

int pop() {

int a = storage[start];

start++;

return a;

}

int front() {

return storage[start];

}

int size() {

return finish - start;

}

String clear() {

finish = 0;

start = 0;

return "ok";

}

String exit() {

return "bye";

}

public class Main {

public static void main(String[] args) throws java.lang.Exception {

String a;

MyQueue x = new MyQueue();

try (Scanner sc = new Scanner(System.in)) {

while (sc.hasNextLine()){

a = sc.next();

if (a.equals("push")) {

int n;

n = sc.nextInt();

x.push(n);

System.out.println("ok");

}

if (a.equals("pop")) {

System.out.println(x.pop());

}

if (a.equals("front")) {

System.out.println(x.front());

}

if (a.equals("size")) {

System.out.println(x.size());

}

if (a.equals("clear")) {

System.out.println(x.clear());

}

if (a.equals("exit")) {

System.out.println(x.exit());

break;

}

Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.

Код на сайте ideone.com находится здесь.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Category Archives: Стеки-деки-очереди

e-olymp 6122. Простой стек

Задача

Тесты

Решение

Пояснения

e-olymp 6127. The queue of unlimited size

Условие

Входные данные

Выходные данные

Тесты:

Код на Java:

Алгоритм:

Ссылки:

e-olimp 6129. Дек неограниченного размера

Задача:

Решение

e-olymp 6123. Стек с защитой от ошибок

Задача

Стек с защитой от ошибок

Входные данные

Выходные данные

Тесты

Решение

e-olymp 6125. Простая очередь

Входные данные

Выходные данные

Тесты

Код